package 力扣题库;

import 剑指offer.ListNode;

public class p160相交链表 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //齐头并进法
        ListNode pl=headA;
        ListNode ps=headB;

        int lenA=0;
        int lenB=0;
        while (pl!=null) {
            lenA++;
            pl=pl.next;
        }
        while (ps!=null) {

            lenB++;
            ps=ps.next;
        }
        pl=headA;
        ps=headB;
        int len=lenA-lenB;
        if (len<0) {
            pl=headB;//headB 节点个数更多，保证 pl始终指向最长的那个链表
            ps=headA;
            len=lenB-lenA;
        }

        //让节点个数多的链表pl，先走 len步
        while (len!=0) {
            pl=pl.next;
            len--;
        }

        while (pl!=ps) {
            pl=pl.next;
            ps=ps.next;
        }
        //pl 和 ps 相遇，其中一个为空，那么这两个链表就没有公共节点
        if (pl==null) {
            return null;
        }
        return pl;
    }
}
